public class Day11 {




    int m,n;
    boolean[][] c;
    int count=0;//路线总数
    int sum=0;//步数
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int p,q;
    public int uniquePathsIII(int[][] grid) {
        m=grid.length;n=grid[0].length;
        c = new boolean[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]==0) sum++;
                else if(grid[i][j]==1) {
                    p=i;
                    q=j;
                }
            }
        }
        sum+=2;
        c[p][q]=true;
        dfs(grid,p,q,1);

        return count;
    }
    public void dfs(int[][] grid,int i,int j,int s) {
        if(grid[i][j]==2) {
            if(sum==s) count++;
            return;
        }

        for(int k=0;k<4;k++) {
            int x=i+dx[k];int y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]!=-1&&!c[x][y]) {
                c[x][y]=true;
                dfs(grid,x,y,s+1);

                c[x][y]=false;
            }
        }
    }



    //1.第k大个元素
    public static void main1(String[] args) {
        int[] arr = {2,1};
        int k = findKthLargest(arr,1);
        System.out.println();
    }
    static int _k=0;
    public static int findKthLargest(int[] nums, int k) {
        qsort(nums,0,nums.length-1,k);
        return _k;
    }
    public static void qsort(int[] a,int start,int end,int k) {
        if(start>=end) {
            _k=a[start];
            return;
        }

        //int key = a[new Random().nextInt(end-start+1)+start];
        int key = a[start];
        int left=start-1;
        int right = end+1;
        int i=start;
        int[] c = {0,0,0};
        while(i<right) {
            if(a[i]<key) {
                swap(a,++left,i++);
                c[0]++;
            }else if(a[i]==key) {
                i++;
                c[1]++;
            }else {
                swap(a,--right,i);
                c[2]++;
            }
        }
        if(c[2]>=k) qsort(a,right,end,k);
        else if(c[1]+c[2]>=k) {
            _k=a[right-1];
        }else  qsort(a,start,left,k-c[1]-c[2]);

    }
    private static void swap(int[] a,int i,int j) {
        int tmp = a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
}
